//
//  ProblemOffer32-3.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/5.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 32 - III. 从上到下打印二叉树 III
 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 例如:
 给定二叉树: [3,9,20,null,null,15,7],
     3
    / \
   9  20
     /  \
    15   7
 返回其层次遍历结果：
 [
   [3],
   [20,9],
   [15,7]
 ]
 提示：节点总数 <= 1000
 */
@objcMembers class ProblemOffer32_3: NSObject {
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(9)
        root.left?.right = TreeNode(10)
        
        root.right = TreeNode(20)
        root.right?.left = TreeNode(15)
        root.right?.right = TreeNode(7)
        print(levelOrder(root))
    }
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        if root == nil {
            return []
        }

        var list:[[Int]] = []
        var nList:[TreeNode] = [root!]
        var l = true
        while nList.isEmpty == false {
            let len = nList.count
            var n = nList.count
            var tempList:[TreeNode] = []
            var tempNum: [Int] = Array(repeating: 0, count: n)
            while n > 0 {
                let node = nList.removeFirst()
                tempNum[l == true ? len-n : n-1] = node.val
                if node.left != nil {
                    tempList.append(node.left!)
                }
                
                if node.right != nil {
                    tempList.append(node.right!)
                }
                n -= 1
            }
            
            list.append(tempNum)
            nList = tempList
            
            l = !l
        }
        
        return list
    }
}
